package com.hdu.hot100.backTrack;

import java.util.ArrayList;
import java.util.List;

public class lc131 {

    class Solution {
        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        public List<List<String>> partition(String s)
        {
            f(s, 0);
            return ans;
        }

        void f(String s, int index)
        {
            if (index == s.length())
            {
                ans.add(new ArrayList<>(path));
            }
            else
            {
                for (int i = index; i < s.length(); i++)
                {
                    if (!isHuiWen(s, index, i))
                    {
                        continue;
                    }
                    String curS = s.substring(index, i + 1);
                    path.add(curS);
                    f(s, i + 1);
                    path.remove(path.size() - 1);
                }
            }
        }

        boolean isHuiWen(String s, int l, int r)
        {
            while (l < r)
            {
                if (s.charAt(l) != s.charAt(r))
                {
                    return false;
                }
                l++;
                r--;
            }
            return true;
        }
    }
}
